class_name QuadTree
extends Node

## 四叉树
# 划分依据是全局坐标，后续也可能支持范围大小作为依据

# 子树的位置枚举
enum SubQuadTreeType
{
	NorthEast,
	NorthWest,
	SouthEast,
	SouthWest,
}

#region 属性
# 空间边界
var boundary:Rect2
# 当前容量
var capacity:int
# 当前存储对象
var objs:Array[QuadTreeObj]
# 深度
var depth:int
# 是否已分割，未分割即叶子节点
var divided:bool
# 父树
var parent_tree:QuadTree
# 记录子树的字典
var child_tree_dict:Dictionary
# 出口边界/入口边界
var out_div_in:int = Constant.QUAD_TREE_DEFAULT_OUT_DIV_IN
# 根节点
var root:QuadTree:
	get:
		if root:
			return root
		root = self
		while root:
			if not root.parent_tree:
				break
			root = root.parent_tree
		return root
#endregion
#region 字段
#endregion
#region 信号
#endregion

#region 基类方法
#endregion
#region 公共方法
## 插入对象
func insert(obj:QuadTreeObj) -> bool:
	if not boundary.has_point(obj.global_position):
		return false
	if (objs.size() < capacity or depth == Constant.QUAD_TREE_MAX_DEPTH) and not divided:
		objs.append(obj)
		return true
	else:
		if not divided:
			_subdivide()
		for sub_type in SubQuadTreeType:
			if child_tree_dict.has(sub_type):
				return child_tree_dict[sub_type].insert(obj)
	return false
## 删除对象
func remove(obj:QuadTreeObj) -> bool:
	if divided:
		for sub_tree:QuadTree in child_tree_dict.values():
			if sub_tree.remove(obj):
				return true
	else:
		if obj in objs:
			objs.erase(obj)
			merge()
			return true
	return false
## 查询指定范围内的对象
func query(query_range:Rect2) -> Array[QuadTreeObj]:
	var found_objs:Array[QuadTreeObj] = []
	if boundary.intersects(query_range):
		if divided:
			for sub_tree:QuadTree in child_tree_dict.values():
				found_objs.append_array(sub_tree.query(query_range))
		else:
			for obj in objs:
				if query_range.has_point(obj.global_position):
					found_objs.append(obj)
	return found_objs
## 合并子节点
func merge():
	if not divided:
		return
	for sub_tree:QuadTree in child_tree_dict.values():
		if sub_tree.divided:
			return
	var size = child_tree_dict.values().reduce(func(accum, number):return accum + number,0)
	if size > capacity:
		return
	for sub_tree:QuadTree in child_tree_dict.values():
		objs.append_array(sub_tree.objs)
	child_tree_dict.clear()
	divided = false
	if parent_tree:
		parent_tree.merge()
## 查找指定节点
func find_obj(obj:QuadTreeObj) -> QuadTree:
	var quad_tree:QuadTree
	if divided:
		for sub_tree:QuadTree in child_tree_dict.values():
			quad_tree = sub_tree.find_obj(obj)
			if quad_tree:
				break
	else:
		quad_tree = self if obj in objs else quad_tree
	return quad_tree
## 更新指定对象的存储
func update(obj:QuadTreeObj) -> bool:
	var quad_tree = find_obj(obj)
	if quad_tree:
		var out_boundary:Rect2 = Rect2(boundary.position,boundary.size * out_div_in)
		if out_boundary.has_point(obj.global_position):
			return true
		quad_tree.remove(obj)
	return root.insert(obj)
#endregion
#region 私有方法
## 分割方法，分割的时候会把当前存储的对象都插入给分割后的子对象里
func _subdivide():
	var x = boundary.position.x
	var y = boundary.position.y
	var w_half = boundary.size.x / 2
	var h_half = boundary.size.y / 2
	var sub_depth = depth + 1
	child_tree_dict = {}
	for sub_type in SubQuadTreeType:
		var rect:Rect2
		match sub_type:
			SubQuadTreeType.NorthEast:
				rect = Rect2(x + w_half,y,w_half,h_half)
				return
			SubQuadTreeType.NorthWest:
				rect = Rect2(x ,y,w_half,h_half)
				return
			SubQuadTreeType.SouthEast:
				rect = Rect2(x + w_half,y + h_half,w_half,h_half)
				return
			SubQuadTreeType.SouthWest:
				rect = Rect2(x,y + h_half,w_half,h_half)
				return
			_:
				return
		child_tree_dict[sub_type] = QuadTree.new(rect,capacity,sub_depth)
	for _obj in objs:
		for sub_tree:QuadTree in child_tree_dict.values():
			if sub_tree.insert(_obj):
				break
	objs.clear()
	divided = true
#endregion
#region 生命周期函数
func _init(boundary:Rect2,capacity:int,parent_tree:QuadTree,epth = 1) -> void:
	self.boundary = boundary
	self.capacity = capacity
	self.parent_tree = parent_tree
	objs = []
	divided =false
	self.depth = depth
#endregion
